정보과학회논문지 (Journal of KIISE)
Current Result Document :
| 한글제목(Korean Title) |
문자열 집합의 순위주기와 순위경계 병렬 계산 |
| 영문제목(English Title) |
Parallel Computation of Order-Preserving Periods and Order-Preserving Borders of a Set of Strings |
| 저자(Author) |
김영호
심정섭
Youngho Kim
Jeong Seop Sim
|
| 원문수록처(Citation) |
VOL 46 NO. 12 PP. 1232 ~ 1240 (2019. 12) |
한글내용
(Korean Abstract) |
정수알파벳으로 구성된 같은 길이의 두 문자열이 주어졌을 때, 두 문자열의 상대적인 순위가 같으면 두 문자열은 순위동형이라 한다. 문자열 �� (�菹� �菹� )의 접두사 �� �偉狼哲� �� �煬� ≤ ≤ �� 와 순위동형인 문자열이 �� 에서 주기적으로 반복되어 나타나면, �� �偉狼哲� �� 의 순위관계표현을 �� 의 순위주기라 한다. 만약 �� 의 접두사 �� �偉狼哲��� �煬� ≤ ≤ �� 와 접미사 �� �� �� �� �狼哲� �� 이 서로 순위동형이면, �� �偉狼哲��� 의 순위관계표현을 �� 의 순위경계라 한다. �� 의 모든 순위주기, 순위경계의 길이는 �� -함수를 이용하여 각각 �� �� log �� 시간에 계산할 수 있다. 본 논문에서는 정수알파벳으로 구성된 길이가 인 문자열들의 집합 �┞냥� �匿� �狼餐� �禮� �哲哲哲� �� �資� 주어졌을 때, �� �� 의 모든 순위주기, 순위경계의 길이를 각각 �� �� �� 개의 스레드를 이용하여 �� �� �� 시간에 계산하는 �� -함수 기반 병렬알고리즘을 제시한다. 실험결과, =1,000, =10,000일 때, 다우존스지수 데이터에 대해 �┞냅� 모든 순위주기, 순위경계의 길이를 계산하는 병렬알고리즘은 각각 기존의 순차알고리즘보다 약 3.47배, 약 3.41배 빠르게 수행되었다.
|
영문내용
(English Abstract) |
Given two strings of the same length over an integer alphabet, those two strings are order-isomorphic when they have the same relative ranks. When strings order-isomorphic to �� �偉狼哲� �� �煬� ≤ ≤ �� are periodically repeated in �� , a representation of the order relations of �� �偉狼哲� �� is referred to as an order-preserving period of �� . When a prefix �� �偉狼哲��� �煬� ≤ ≤ �� of �� is order-isomorphic to a suffix �� �� �� �� �狼哲� �� of �� , a representation of the order relations of �� �偉狼哲��� is called an order-preserving border of �� . The lengths of all order-preserving periods (resp. all order-preserving borders) of �� can be computed in �� �� log �� time using the �� -function. Given a set �┞냥� �匿� �狼餐� �禮� �哲哲哲� �� �� of strings of length over an integer alphabet, we propose parallel algorithms computing the lengths of all order-preserving periods and all order-preserving borders of �┞� using �� �� �� threads in �� �� �� time by the �� -function. When compared to each sequential algorithm for Dow Jones Industrial Average, the experimental results show that our parallel algorithm for computing the lengths of all order-preserving periods (resp. all order-preserving borders) of �┞� runs approximately 3.47 (resp. 3.41) times faster when =1,000, =10,000.
|
| 키워드(Keyword) |
순위패턴매칭
순위주기
순위경계
병렬알고리즘
GPU
order-preserving pattern matching
order-preserving periods
order-preserving borders
parallel algorithm
GPU
|
| 파일첨부 |
PDF 다운로드
|
